
public class test {
    //leetcode 416.分割等和子集
    class Solution {
        // 二维解法 -> 01背包(恰好装满)
        public boolean canPartition1(int[] nums) {
            // 假设和为s
            // 如果想分为两个子集元素和相等则
            // s % 2 == 0, s1 = s2 = s/2
            int n = nums.length;
            int sum = 0;
            for(int i = 0;i < n;i++){
                sum += nums[i];
            }
            if(sum % 2 != 0){
                return false;
            }
            // 1. 创建 dp 表
            int N = sum / 2;
            int[][] dp = new int[n + 1][N + 1];
            // 2. 初始化
            //-1代表空间为 j 时不存在(装不满)
            for(int i = 1;i <= N;i++){
                dp[0][i] = -1;
            }
            // 3. 填表
            for(int i = 1;i <= n;i++){
                for(int j = 1;j <= N;j++){
                    dp[i][j] = dp[i-1][j];
                    if(j >= nums[i - 1] && dp[i-1][j - nums[i - 1]] != -1){
                        dp[i][j] = Math.max(dp[i][j],dp[i-1][j - nums[i - 1]] + nums[i - 1]);
                    }
                }
            }
            // 4. 返回值
            return dp[n][N] != -1;
        }
        // 一维解法 -> 01背包(空间优化)
        public boolean canPartition(int[] nums){
            int n = nums.length;
            int sum = 0;
            for(int i = 0;i < n;i++){
                sum += nums[i];
            }
            if(sum % 2 != 0){
                return false;
            }
            int N = sum / 2;
            int[] dp = new int[N + 1];
            for(int i = 1;i <= N;i++){
                dp[i] = -1;
            }
            for(int i = 1;i <= n ;i++){
                for(int j = N;j >= 0;j--){
                    if(j >= nums[i - 1] && dp[j - nums[i - 1]] != -1){
                        dp[j] = Math.max(dp[j],dp[j - nums[i - 1]] + nums[i - 1]);
                    }
                }
            }
            return dp[N] != -1;
        }
    }
    //leetcode 494.目标和
    class Solution {
        // 二维解法 -> 01背包
        public int findTargetSumWays1(int[] nums, int target) {
            int n = nums.length;
            int sum = 0;
            for(int i = 0;i < n;i++){
                sum += nums[i];
            }
            if(Math.abs(target) > sum || (sum + target) % 2 != 0){
                return 0;
            }
            // 1. 创建 dp 表
            // 若能求出目标和,则
            //(正数 + 负数) = target
            //(正数 - 负数) = sum
            //得 正数 = (sum + target) / 2;求出能得到多少次正数即可.
            int newTarget = (sum + target) / 2;
            //前 i 个元素中,和为 j 的个数
            int[][] dp = new int[n + 1][newTarget + 1];
            // 2. 初始化
            dp[0][0] = 1;
            // 3. 填表
            for(int i = 1;i <= n;i++){
                for(int j = 0;j <= newTarget;j++){
                    dp[i][j] = dp[i-1][j];
                    if(j >= nums[i - 1]){
                        dp[i][j] += dp[i - 1][j - nums[i - 1]];
                    }
                }
            }
            // 4. 返回值
            return dp[n][newTarget];
        }
        // 一维解法 -> 01背包(空间优化)
        public int findTargetSumWays(int[] nums,int target){
            int n = nums.length;
            int sum = 0;
            for(int i = 0;i < n;i++){
                sum += nums[i];
            }
            if(Math.abs(target) > sum || (sum + target) % 2 != 0){
                return 0;
            }
            int newTarget = (sum + target) / 2;
            int[] dp = new int[newTarget + 1];
            dp[0] = 1;
            for(int i = 1;i <= n;i++){
                for(int j = newTarget;j >= 0;j--){
                    if(j >= nums[i - 1]){
                        dp[j] += dp[j - nums[i - 1]];
                    }
                }
            }
            return dp[newTarget];
        }
    }
}